//class Solution {
//public:
//    void merge(vector<int>& A, int m, vector<int>& B, int n) {
//        int end = m + n - 1, end1 = m - 1, end2 = n - 1;
//        while (end1 >= 0 && end2 >= 0)
//        {
//            if (A[end1] > B[end2])
//                A[end--] = A[end1--];
//            else
//                A[end--] = B[end2--];
//        }
//        while (end2 >= 0)
//            A[end--] = B[end2--];
//        return;
//    }
//};



class Solution {
public:
	bool next_permutation(string& s)
	{
		int n = s.size();
		for (int i = n - 2; i >= 0; i--)
		{
			if (s[i] < s[i + 1])
			{
				int j = n - 1;
				for (; s[j] <= s[i]; j--);
				swap(s[i], s[j]);
				reverse(s.begin() + i + 1, s.end());
				return true;
			}
		}
		return false;
	}
	vector<string> permutation(string s)
	{
		vector<string>result;
		sort(s.begin(), s.end());
		do
		{
			result.push_back(s);
		} while (next_permutation(s));
		return result;
	}
};